﻿// 0729train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>
#include <stack>
#include <queue>

using namespace std;


/*
 找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。
 如果不存在下一个更大元素，那么本次查询的答案是 -1 。

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 */

void SetResultValue(vector<int>&result, 
    unordered_map<int, int>index_map,
    int curr_num, int value
)
{
    if (index_map.count(curr_num))
    {
        int index = index_map[curr_num];
        result[index] = value;
    }
}

void solve01(vector<int>nums1, vector<int>nums2)
{
    int result_size = nums1.size();
    vector<int>result(result_size);

    unordered_map<int, int>index_map;
    for (int i=0;i<nums1.size();i++)
    {
        int curr_num = nums1[i];
        index_map[curr_num] = i;
    }
    stack<int>oh_stack;
    int nums2_size = nums2.size();
    for (int i = nums2_size-1; i>=0; i--)
    {
        int curr_num = nums2[i];
	    if (oh_stack.empty())
	    {
            SetResultValue(result, index_map, curr_num, -1);
            oh_stack.push(curr_num);
            continue;
	    }
        while (!oh_stack.empty()&&oh_stack.top()<curr_num)
        {
            oh_stack.pop();
        }
        if (oh_stack.empty())
        {
            SetResultValue(result, index_map, curr_num, -1);
        }
        else
        {
            int target = oh_stack.top();
            SetResultValue(result, index_map, curr_num, target);
        }
        oh_stack.push(curr_num);
    }

    for (auto&item:result)
    {
        cout << item << ' ';
    }

    //solve01
    //------
}


/*
 在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，
 i 右边第一个更高 j，那么j是i的好朋友（j > i）。
 请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，
 如果没有看到好朋友，请在该位置用0代替。小朋友人数范围是 [0, 40000]。
输入描述
第一行输入N，表示有N个小朋友
第二行输入N个小朋友的身高height[i]，都是整数
输出描述
输出N个小朋友的好朋友的位置

输入
2
100 95

输出
0 0


输入
8
123 124 125 121 119 122 126 123
输出
1 2 6 5 5 6 0 0

 */
void solve02(vector<int>&oh_vec)
{
    int oh_vec_size = oh_vec.size();
    stack<int>oh_stack;
    vector<int>result_vec(oh_vec_size, 0);

    for (int i=oh_vec_size-1; i>=0; i--)
    {
        int curr_num = oh_vec[i];

        while (!oh_stack.empty() && oh_vec[oh_stack.top()]<= curr_num)
        {
            oh_stack.pop();
        }

        if (!oh_stack.empty())
        {
            result_vec[i] = oh_stack.top();
        }
        oh_stack.push(i);

        //for------
    }

    for (int i=0;i<result_vec.size();i++)
    {
        int curr_num = result_vec[i];
        if (i!= result_vec.size()-1)
        {
            cout << curr_num << ' ';
        }
        else
        {
            cout << curr_num;
        }
    }

    //solve02
    //------
}


int main()
{
	{
        //8
		//123 124 125 121 119 122 126 123
        int vec_size;
        cin >> vec_size;
        vector<int>oh_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            cin >> oh_vec[i];
        }

        //for (auto&item:oh_vec)
        //{
        //    cout << item << ' ';
        //}

        //vector<int>oh_vec = { 123,124,125,121,119,122,126,123 };
        solve02(oh_vec);
        return 0;
	}

    vector<int>nums1 = { 4, 1, 2 }, nums2 = { 1, 3, 4, 2 };

    solve01(nums1, nums2);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
